// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
//图-邻接矩阵+Prim+Dijistra
#include "stdafx.h"
#include <iostream>
#include "string"
using namespace std;
const int MaxSize = 100;
const int Maxcost = 99999;
static int visited[MaxSize] = { 0 };

//辅助数组
struct ShortEdge
{
	char adjvex;
	int lowcost;
};

template <class DataType>
class MGraph
{
public:
	MGraph(DataType a[], int n, int e);
	~MGraph() {}
	void DFSTraverse(int v);
	void BFSTraverse(int v);
	friend void Prim(MGraph<char> G);
	friend void Dijikstra(MGraph<char> G,int v);
private:
	DataType vertex[MaxSize];
	int arc[MaxSize][MaxSize];
	int vertexNum, arcNum;
};
//构造函数
template<class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e)
{
	vertexNum = n;
	arcNum = e;
	for (int i = 0; i<n; i++)
	{
		vertex[i] = a[i];
		for (int j = 0; j<n; j++)
		{
			if (i == j)
				arc[i][j] = 0;
			else
			arc[i][j] = Maxcost;
		}
	}
	cout << "请输入边依附的顶点编号及权值：" << endl;
	for (int k = 0; k<e; k++)
	{
		int i, j,p;
		cin >> i >> j>> p;
		arc[i][j] = p;
		//arc[j][i] = p;
	}
}
//深度优先
template <class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{
	cout << vertex[v] << " ";
	visited[v] = 1;
	for (int i = 0; i<vertexNum; i++)
	{
		if (arc[v][i] > 0 && visited[i] == 0)
			DFSTraverse(i);
	}
}
//广度优先
template<class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{
	for (int p = 0; p < MaxSize; p++) {
		visited[p] = 0;
	}
	int Q[MaxSize] = { 0 };
	int front = -1;
	int	rear = -1;
	cout << vertex[v] << " ";
	visited[v] = 1;
	Q[++rear] = v;
	while (front != rear)
	{
		v = Q[++front];
		for (int i = 0; i < vertexNum; i++)
		{
			if (arc[v][i] > 0 && visited[i] == 0)
			{
				cout << vertex[i] << " ";
				visited[i] = 1;
				Q[++rear] = i;
			}
		}
	}
}

//寻找最短边算法
int MinEdge(ShortEdge s[], int vertexNum)
{
	int k = 1;
	for (int i = 2; i < vertexNum; i++)
	{
		if (s[i].lowcost!=0&&(s[i].lowcost < s[k].lowcost))
			k = i;
	}
	return k;
}

//Prim算法
void Prim(MGraph<char> G)
{
	ShortEdge s[MaxSize];
	int i = 0;
	s[0].adjvex = G.vertex[0];
	for (i = 1; i < G.vertexNum; i++)
	{
		s[i].lowcost = G.arc[0][i];
		s[i].adjvex = G.vertex[0];
	}
	s[0].lowcost = 0;
	for (int j = 1;j < G.vertexNum; j++)
	{
		int k = MinEdge(s, G.vertexNum);
		cout << "(" << s[k].adjvex << "," << G.vertex[k] << ")" << s[k].lowcost << endl;
		s[k].lowcost = 0;
		for (i = 1; i < G.vertexNum; i++)
		{
			if (G.arc[k][i] < s[i].lowcost)
			{
				s[i].lowcost = G.arc[k][i];
				s[i].adjvex = G.vertex[k];
			}
		}
	}
}

//最短路径Dijistra算法

void Dijikstra(MGraph<char> G,int v)
{
        int dist[MaxSize];
        string path[MaxSize];
        path[0]="hello";
        
	int i, k;
	for ( i = 0; i < G.vertexNum; i++)
	{
		dist[i] = G.arc[v][i];
		if (dist[i] != Maxcost)
                {
			path[i] = G.vertex[v] + G.vertex[i];
                cout<<path[i];
                }
		else
		{
			path[i] = "";
		}
	}
	int S[MaxSize];
	S[0] = v;
	dist[v] = 0;
	int num = 1;
	while (num < G.vertexNum)
	{
		for (k = 0, i = 0; i < G.vertexNum; i++)
		{
			if ((dist[i] != 0) && (dist[i] < dist[k]))
			{
				k = i;
			}
			cout << dist[k] << path[k];
			S[num++] = k;
			for (int i = 0; i < G.vertexNum; i++)
			{
				if (dist[i] > dist[k] + G.arc[k][i])
				{
					dist[i] = dist[k] + G.arc[k][i];
					path[i] = path[i] + G.vertex[i];
				}
				dist[k] = 0;
			}
		}
	}
}

int main()
{
	int n, e;
	char a[MaxSize];
	cout << "请输入顶点个数：";
	cin >> n;
	cout << "\n请输入边的条数：";
	cin >> e;
	cout << "\n请输入顶点，空格隔开：";
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	MGraph<char> m1(a, n, e);
	cout << "深度优先遍历：";
	m1.DFSTraverse(0);
	cout << endl;
	cout << "广度优先遍历：";
	m1.BFSTraverse(0);
	cout << endl;
	cout << "最小生成树为："<<endl;
	Prim(m1);
        Dijikstra(m1,0);
	return 0;
}




